﻿/*
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
*/

#include "AllInc.h"

class Solution {
public:
	vector<int> topKFrequent(vector<int>& nums, int k) 
	{
		unordered_map<int, int> record;
		size_t len = nums.size();
		for (size_t i = 0; i < len; i++)
		{
			record[nums[i]]++;
		}

		priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
		for (auto it = record.begin(); it != record.end(); it++)
		{
			if (pq.size() == k)
			{
				if (pq.top().first < it->second)
				{
					pq.pop();
					pq.push(make_pair(it->second, it->first));
				}
			}
			else
			{
				pq.push(make_pair(it->second, it->first));
			}
		}

		vector<int> result;
		while (!pq.empty())
		{
			result.push_back(pq.top().second);
			pq.pop();
		}

		return result;
	}
};

//int main()
//{
//	Solution s;
//	vector<int> data{ 1, 2, 3, 1, 2, 3 };
//	auto result = s.topKFrequent(data, 2);
//
//	return 0;
//}